package com.yaoxiaoqing.basis;

import java.util.Arrays;

/**
 * 数组元素的排序算法
 * 排序：假设含有 n 个记录的序列为{R1，R2，…,Rn},其相应的关键字序列为{K1，K2，…,Kn}。将这些记录重新排序为{Ri1,Ri2,…,Rin},使得相应的关键字值满足条 Ki1<=Ki2<=…<=Kin,这样的一种操作称为排序。
 * 通常来说，排序的目的是快速查找。
 * 衡量排序算法的优劣：
 * 时间复杂度：分析关键字的比较次数和记录的移动次数
 * 空间复杂度：分析排序算法中需要多少辅助内存
 * 稳定性：若两个记录 A 和 B 的关键字值相等，但排序后 A、B 的先后次序保持不变，则称这种排序算法是稳定的。
 * 排序算法分类：内部排序和外部排序。
 * 内部排序：整个排序过程不需要借助于外部存储器（如磁盘等），所有排序操作都在内存中完成。
 * 外部排序：参与排序的数据非常多，数据量非常大，计算机无法把整个排序过程放在内存中完成，必须借助于外部存储器（如磁盘）。外部排序最常见的是多路归并排序。可以认为外部排序是由多次内部排序组成。
 十大内部排序算法
 选择排序
 直接选择排序、堆排序
 交换排序
 冒泡排序、快速排序
 插入排序
 直接插入排序、折半插入排序、Shell 排序
 归并排序
 桶式排序
 基数排序
 https://blog.csdn.net/PorkBird/article/details/113694291
 */
public class ArraySort {
    public static void main(String[] args) {
     //冒泡排序
        BubbleSort();
        //快速排序
        QuickSort();
    }

    /**
     * 冒泡排序
     * 冒泡排序的基本思想：通过对待排序序列从前向后，依次比较相邻元素的排序码，若发现逆序则交换，使排序码较大的元素逐渐从前部移向后部。
     * 因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序， 因此要在排序过程中设置一个标志swap判断元素是否进行过交换。从而减少不必要的比较。
     */
    public  static void BubbleSort(){
        int[] arr = new int[]{43,32,76,92,-65,85,71,-42};
        for (int i = 0; i < arr.length-1; i++) {//只需要遍历数组长度-1次 需要遍历的趟数
            for (int j = 0; j<arr.length-1-i ; j++) {//当前趟遍历的次数
                //如果当前元素比后面的大，那么就交换
                if(arr[j]>arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+"\t");
        }
    }

    public  static  void  QuickSort(){
        int[] data = { 9, -16, 30, 23, -30, -49, 25, 21, 30 };
        System.out.println("排序之前：\n" +Arrays.toString(data));
        subSort(data, 0, data.length - 1);
        System.out.println("排序之后：\n" +Arrays.toString(data));
    }

    public static void subSort(int[] data, int start, int end) {
        if(start<end){
            int base = data[start];//拿到data第一个值
            int low = start;//开始的索引
            int high = end + 1;//数组的长度

            while (true){
                while (low<end&&data[++low]-base<=0 )
                    ;
                while (high>start&&data[--high]-base>=0)
                    ;
                if(low<high){
                    swap(data, low, high);
                }else{
                    break;
                }
            }
            swap(data, start, high);

            subSort(data, start, high - 1);//递归调用
            subSort(data, high + 1, end);
        }
    }
    private static void swap(int[] data, int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}
